package leetcode;
/**
 * 494.目标和
 * 给定⼀个⾮负整数数组，a1, a2, ..., an, 和⼀个⽬标数S。现在你有两个符号 + 和 -。对于数组中的任意
 * ⼀个整数，你都可以从 + 或 -中选择⼀个符号添加在前⾯。
 * 返回可以使最终数组和为⽬标数 S 的所有添加符号的⽅法数。示例：
 * 输⼊：nums: [1, 1, 1, 1, 1], S: 3
 * 输出：5 解释：
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 * ⼀共有5种⽅法让最终⽬标和为3。
 * 提示：
 *    数组⾮空，且⻓度不会超过 20 。
 *    初始的数组的和不会超过 1000 。
 *    保证返回的最终结果能被 32 位整数存下。
 *
 * 思路：
 *    如何能转化成01背包问题呢？ 想想，看看有多么的灵性~
 *    假设前面+号的数总和为x, 则前面-号的数总和为(sum-x), 满足 x-(sum-x)=S
 *    最终化简得到 x=(S+sum)/2
 *    这不就是01背包问题吗？ 在这些整数中找一部分数之和为x，求有多少种找法？
 */
public class Num_494 {
    public static void main(String[] args) {
        System.out.println(findTargetSumWays(new int[]{1,1,1,1,1},3)); // 5
        System.out.println(findTargetSumWays(new int[]{1,0},1)); // 2
        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,1},1)); // 256
        int[] s = new int[]{2,107,109,113,127,131,137,3,2,3,5,7,11,13,17,19,23,29,47,53};
        System.out.println(findTargetSumWays(s,1000)); // 0
        System.out.println(findTargetSumWays(new int[]{0},0)); // 2
    }
    public static int findTargetSumWays(int[] nums, int target) {//2^8=128*2=256
        //求总和
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //没有方案的情况: x%2!=0 、 x<0 、 x>sum
        if((target+sum)%2 != 0 || (target+sum)/2 < 0 || (target+sum)/2 > sum){
            return 0;
        }
        //找凑出和为x的方法数
        int x = (target + sum) / 2;
        //凑m，降低时间复杂度
        int m = Math.min(x,sum-x);

        //dp[i][j]表示前i个整数凑出j的方法数
        int[][] dp = new int[nums.length+1][m+1];
        /** 这个初始化有点难度 **/
        dp[0][0] = 1;
        for(int i=1; i<=nums.length; i++){
            //需要考虑整数是否本身为0？
            if(nums[i-1] != 0){
                //前i个整数凑出0的方法==前i-1个整数凑出0的方法
                dp[i][0] = dp[i-1][0];
            }else{
                //前i个整数凑出0的方法==前i-1个整数凑出0的方法*2，因为存在选和不选两种情况
                dp[i][0] = dp[i-1][0] * 2;
            }
        }
        //开始遍历填写dp数组
        for(int i=1; i<=nums.length; i++){
            for(int j=1; j<=m; j++){
                //不选第i个整数
                dp[i][j] += dp[i-1][j];
                //选第i个整数
                if(nums[i-1] <= j){
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[nums.length][m];
    }
}
